#include "BinaryLinkTree.h"
#include <iostream>

BinaryLinkTree::BinaryLinkTree()
{
    root = nullptr; //二叉树可以为空，所以可以直接初始化为空
}

BinaryLinkTree::~BinaryLinkTree()
{
}

/* 调用插入函数 */
void BinaryLinkTree::Insert(ElementType element)
{
    // if(root == nullptr)
    // {
    //     root = new Node(element);
    // }
    // else
    // {
    //     //二叉树左边比根小，右边比根大
    //     InsertNode(root,element);   //从root开始插入
    // }
    root = InsertNode(root,element);
}

void BinaryLinkTree::Remove(ElementType element)
{
    root = RemoveNode(root,element);//!!!root要换的，一定要写root= 
}

void BinaryLinkTree::show()
{
    PrevTravel(root,showPtr);
    std::cout<<std::endl;
    MidTravel(root,showPtr);
    std::cout<<std::endl;
    PostTravel(root,showPtr);
    std::cout<<std::endl;
}

/* 插入节点 */
//要注意在根节点之前就可能出现失衡情况！！！！
BLTree::Node * BinaryLinkTree::InsertNode(Node *node, ElementType element)
{
    //如果没有节点为空，则创建节点
    if(node == nullptr)    
        return new Node(element);   //创建节点  //插入1的时候直接创建一个头节点

    //节点的值等于element，也不插入
    if(node->data == element)
        return node;

    //插入到左子树
    if(element < node->data)
    {
        //递归插入
        node->left = InsertNode(node->left,element);
        // if(node->left == nullptr)
        // {
        //     node->left = new Node(element); //变成node的孩子
        //     node->left->parent = node;      //node是left的双亲
        // }
        // else
        //     InsertNode(node->left,element); //左边不为空直接递归
        
        //失衡-左子树重
        if(LeftRightDeviation(node) > 1)
        {
            //左左失衡
            if(element < node->left->data)
            {
                node = RotateRight(node);
            }
            //左右失衡
            else
            {
                node = RotateLeftRight(node);
            }
        }
    }
    else
    {
        node->right = InsertNode(node->right,element);
        // if(node->right == nullptr)
        // {
        //     node->right = new Node(element);
        //     node->right->parent = node;
        // }
        // else
        //     InsertNode(node->right,element);
        if(LeftRightDeviation(node) < -1)
        {
            //右左失衡
            if(element < node->right->data)
            {
                node = RotateRightLeft(node);
            }
            //右右失衡
            else
            {
                node = RotateLeft(node);
            }
        }
    }
    return node;
}

BLTree::Node *BinaryLinkTree::RemoveNode(Node *node, ElementType element)
{
    if(node == nullptr)
        return node;
    if(element < node->data)
    {
        node->left = RemoveNode(node->left,element);
    }
    else if(element > node->data)
    {
        node->right = RemoveNode(node->right,element);
    }
    else
    {
        //只有一个孩子或左右都没有孩子
        if(node->left == nullptr || node->right == nullptr)
        {
            Node * temp = node->left ? node->left : node->right;
            //叶子，删除叶子
            if(temp == nullptr)
            {
                delete node;
                node = nullptr;//不能return nullptr
            }
            else
            {
                temp->parent = node->parent;
                delete node;
                node = temp;
            }
        }
        //有两个孩子
        else//重新听一下
        {
            Node * min = GetMinNode(node->right);
            node->data = min->data;
            node->right = RemoveNode(node->right,min->data);
        }
    }

    if(node == nullptr)
        return node;
    //左子树重
    if(LeftRightDeviation(node) > 1)
    {
        //左子树的左边更重 左左
        if(LeftRightDeviation(node->left) > 0)  //为什么大于0
        {
            node = RotateRight(node);
        }
        //左右
        else
        {
            node = RotateLeftRight(node);
        }
    }
    else if(LeftRightDeviation(node) < -1)
    {
        //右左
        if(LeftRightDeviation(node->right) > 0)
        {
            node = RotateRightLeft(node);
        }
        //右右
        else
        {
            node = RotateLeft(node);
        }
    }
    return node;//经过以上操作，返回node
}

BLTree::Node *BinaryLinkTree::GetMinNode(Node *node)
{
    Node * min = node;
    while(min->left != nullptr)
    {
        min = min->left;
    }
    return min;
}

ElementType *BinaryLinkTree::FindNode(Node *node, ElementType element)
{
    if(node == nullptr)
        return nullptr;
    if(node->data == element)
        return & node->data;
    else if(node->data > element)
    {
        return FindNode(node->left,element);
    }
    else
    {
        return FindNode(node->right,element);
    }
}

ElementType *BinaryLinkTree::FindNode(ElementType element)//返回值为int*，因为int没法判断非法值，要用指针来判断
{

    return FindNode(root,element);
}

/* ………………遍历输出……………… */
/*前序遍历*/
void BinaryLinkTree::PrevTravel(Node *node,void(*showPtr)(ElementType))
{
    if(node == nullptr)
        return;
    //std::cout<<node->data<<" "; //中
    showPtr(node->data);
    PrevTravel(node->left,showPtr);     //左
    PrevTravel(node->right,showPtr);    //右
}
/*中序遍历*/
void BinaryLinkTree::MidTravel(Node *node,void(*showPtr)(ElementType))
{
    if(node == nullptr)
        return;
    MidTravel(node->left,showPtr);     //左
    //std::cout<<node->data<<" "; //中
    showPtr(node->data);
    MidTravel(node->right,showPtr);    //右
}
/*后序遍历*/
void BinaryLinkTree::PostTravel(Node *node,void(*showPtr)(ElementType))
{
    if(node == nullptr)
        return;
    PostTravel(node->left,showPtr);     //左
    PostTravel(node->right,showPtr);    //右
    //std::cout<<node->data<<" "; //中
    showPtr(node->data);
}

/* 求高度 */
int BinaryLinkTree::GetNodeHeight(Node *node)
{
    if(node == nullptr)
        return 0;
    int lh = GetNodeHeight(node->left);//二叉树只需要考虑两个孩子
    int rh = GetNodeHeight(node->right);
    return (lh > rh ? lh : rh) + 1;
}

/* 判断是否平衡 */
int BinaryLinkTree::LeftRightDeviation(Node *node)
{
    //abs绝对值
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}

/* ………………失衡旋转……………… */
/* 左旋 */
BLTree::Node *BinaryLinkTree::RotateLeft(Node *node)
{
    Node * t = node->right;
    node->right = t->left;
    t->left = node;

    t->parent = node->parent;
    node->parent = t;
    return t;
}
/* 右旋 */
BLTree::Node *BinaryLinkTree::RotateRight(Node *node)
{
    Node * t = node->left;
    node->left = t->right;
    t->right = node;//

    t->parent = node->parent;
    node->parent = t;
    return t;
}
/* 左右旋 */
BLTree::Node *BinaryLinkTree::RotateLeftRight(Node *node)
{
    //先把左子树左旋
    node->left = RotateLeft(node->left);
    //再进行右旋，返回新的根
    return RotateRight(node);
}
/* 右左旋 */
BLTree::Node *BinaryLinkTree::RotateRightLeft(Node *node)
{
    //先把右子树右旋
    node->right = RotateRight(node->right);
    //再进行右旋，返回新的根
    return RotateLeft(node);
}

void BLTree::SetShowtype(void(*showPtr)(ElementType))
{
    this->showPtr = showPtr;
}
